// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
func hIndex1(citations []int) int {
    left, right := 0, len(citations)
    for left < right {
        mid := left + (right - left + 1) / 2

        cnt := 0
        for _, v := range citations {
            if v >= mid {
                cnt++
            }
        }

        if cnt >= mid {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

func hIndex2(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    // bug 修复，h 不能等于 0，否则数组越界异常
    for h := n; h > 0; h-- {
        if citations[n-h] >= h {
            return h
        }
    }
    return 0
}

func hIndex3(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    left, right := 0, n
    for left < right {
        h := left + (right-left+1)/2
        if citations[n-h] >= h {
            left = h
        } else {
            right = h - 1
        }
    }
    return left
}

func hIndex(citations []int) int {
    n := len(citations)
    counter := make([]int, n + 1)
    for i := 0; i < n; i++ {
        if citations[i] >= n {
            counter[n]++
        } else {
            counter[citations[i]]++
        }
    }

    total := 0
    for h := n; h >= 0; h-- {
        total += counter[h]
        if total >= h {
            return h
        }
    }

    return 0
}